package algorithm;

import java.util.Comparator;
import java.util.PriorityQueue;

public class sortMethod {

    public static int[] array = {3, 1, 4, 13, 12, 141, 10, 20};

    static void bubbleSort(){
        int l = array.length;
        for(int i = 0; i < l; i ++) {
            for(int j = 0; j < l - i - 1; j ++) {
                if(array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    static void insertSort(){
        int l = array.length;
        for(int i = 1; i < l; i ++) {
            int j = i - 1;
            int target = array[i];
            while(j >= 0 && array[j] > target) {
                array[j+1] = array[j];
                j --;
            }
            array[j + 1] = target;
        }
    }

    static void chooseSort(){
        int l = array.length;
        for(int i = l; i > 0; i --) {
            int temp = Integer.MIN_VALUE;
            int loc = -1;
            for(int j = 0; j < i; j ++) {
                if(array[j] > temp) {
                    temp = array[j];
                    loc = j;
                }
            }
            array[loc] = array[i - 1];
            array[i - 1] = temp;
        }
    }

    static void bucketSort(){
        int l = array.length;
        int[] temp = new int[l];

        for(int i = 1; i < l * 2; i = i << 1){
            int index = 0;
            for(int j = 0; j < l; j += i * 2){
                int l1 = j, r1 = Math.min(j + i, l);
                int l2 = r1, r2 = Math.min(j + 2 * i, l);
                int left = l1, right = l2;
                while(left < r1 &&  right < r2) {
                    if(array[left] < array[right]) {
                        temp[index] = array[left];
                        left += 1;
                    }else{
                        temp[index] = array[right];
                        right += 1;
                    }
                    index += 1;
                }
                while(left < r1){
                    temp[index] = array[left];
                    left += 1;
                    index += 1;
                }
                while(right < r2) {
                    temp[index] = array[right];
                    right += 1;
                    index += 1;
                }
            }
            for(int k = 0; k < l; k ++) {
                array[k] = temp[k];
            }
        }
        for(int k = 0; k < l; k ++) {
            array[k] = temp[k];
        }
    }

    static void quickSort(int left, int right){
        if(left >= right) return;
        int target = array[left];
        int l = left, r = right;
        while(l < r) {
            // 寻找右边第一个比它小的数字，放到l所指的地方
            while(r > l && target < array[r]) r--;
            if(r > l) array[l++] = array[r];

            // 寻找左边第一个比它大的数字，放到r所指的地方
            while(l < r && target > array[l]) l++;
            if(l < r) array[r--] = array[l];
        }
        array[l] = target;
        quickSort(left, l-1);
        quickSort(l+1, right);
    }

    //面试这么写堆排序，面试官都笑了，哈哈哈，正确的堆排序方法见下边的静态内部类
//    static void heapSort(){
//        PriorityQueue<Integer> container = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o1 - o2;
//            }
//        });
//        for(int i = 0; i < array.length; i ++) {
//            container.add(Integer.valueOf(array[i]));
//        }
//        int count = 0;
//        while(!container.isEmpty()){
//            array[count++] = container.poll();
//        }
//    }

    static class heapSort{
        private static int[] nums = new int[100];
        private static int end = 0;

        heapSort(int[] array){
            for(int i = 0; i < array.length; i ++) {
                nums[i] = array[i];
                end += 1;
            }
            for(int i = end - 1; i >= 0; i --) {
                downHeap(i);
            }
        }

        private static void swap(int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        private static void downHeap(int i){
            while(i < end){
                if(2*i +1 >= end) break;
                int left = nums[2*i+1], right = nums[2*i+2];
                if(left > right){
                    swap(i, 2*i +1);
                    i = 2*i+1;
                }else{
                    swap(i, 2*i+2);
                    i = 2*i+2;
                }
            }
        }

        public void sort(){
            int length = end;
           for(int i = 0; i < length; i ++) {
               System.out.printf("%d ", nums[0]);
               nums[0] = -1;
               swap(0, end-1);
               end -= 1;
               downHeap(0);
           }

        }
    }
    public static void main(String[] args) {
        heapSort temp = new heapSort(array);
        temp.sort();


//        sortMethod.heapSort();
//        sortMethod.quickSort(0, sortMethod.array.length-1);
//        sortMethod.bucketSort();
//        sortMethod.chooseSort();
//        sortMethod.insertSort();
//        sortMethod.bubbleSort();

//        for(int cur: sortMethod.array) {
//            System.out.printf("%d ", cur);
//        }
//        System.out.printf("\n");
    }

}
